package com.cb2.algorithm.leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

/**
 * <a href='https://leetcode.cn/problems/jump-game-iv/'>跳跃游戏 IV(Jump Game IV)</a>
 * <p>给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。</p>
 * <p>每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ：
 * <ul>
 *     <li>i + 1 需满足：i + 1 < arr.length</li>
 *     <li>i - 1 需满足：i - 1 >= 0</li>
 *     <li>j 需满足：arr[i] == arr[j] 且 i != j</li>
 * </ul></p>
 * <p>请你返回到达数组最后一个元素的下标处所需的 最少操作次数。</p>
 * <p>注意：任何时候你都不能跳到数组外面。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：arr = [100,-23,-23,404,100,23,23,23,3,404]
 *      输出：3
 *      解释：那你需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的最后一个元素的下标。
 *
 * 示例 2：
 *      输入：arr = [7]
 *      输出：0
 *      解释：一开始就在最后一个元素处，所以你不需要跳跃。
 *
 * 示例 3：
 *      输入：arr = [7,6,9,6,9,6,9,7]
 *      输出：1
 *      解释：你可以直接从下标 0 处跳到下标 7 处，也就是数组的最后一个元素处。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= arr.length <= 5 * 10^4</li>
 *     <li>-10^8 <= arr[i] <= 10^8</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/2/18 11:02
 */
public class LC1345JumpGame_IV_H {
    static class Solution {
        public int minJumps(int[] arr) {
            // 值，值相同的所有索引集
            Map<Integer, List<Integer>> val2sameValIdxMap = new HashMap<>();
            for (int i = 0; i < arr.length; i++) {
                val2sameValIdxMap.putIfAbsent(arr[i], new ArrayList<>());
                val2sameValIdxMap.get(arr[i]).add(i);
            }
            Set<Integer> visitedIdx = new HashSet<>();
            Queue<int[]> idxStepQueue = new ArrayDeque<>();
            idxStepQueue.offer(new int[]{0, 0});   // 从idx 0出发，需要0步
            visitedIdx.add(0);
            while (!idxStepQueue.isEmpty()) {
                int[] idxStep = idxStepQueue.poll();
                int idx = idxStep[0];   // 当前索引
                int step = idxStep[1];  // 到达当前索引所需步骤
                // 如果到达数组最后一个元素的下标处
                if (idx == arr.length - 1) {
                    return step;
                }
                // 处理当前idx可到达的位置，需要跳跃一步
                step++;
                // 1.处理值相同的idx
                int val = arr[idx];
                if (val2sameValIdxMap.containsKey(val)) {
                    for (int i : val2sameValIdxMap.get(val)) {
                        idxStepQueue.offer(new int[]{i, step});
                    }
                }
                // 2.处理当前idx的next
                if (idx + 1 < arr.length && visitedIdx.add(idx + 1)) {
                    idxStepQueue.offer(new int[]{idx + 1, step});
                }
                // 处理当前idx的prev
                if (idx - 1 >= 0 && visitedIdx.add(idx - 1)) {
                    idxStepQueue.offer(new int[]{idx - 1, step});
                }
            }
            return -1;
        }
    }
}